/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/heapify
   @Language: C++
   @Datetime: 16-02-09 05:52
   */

// Method 1, Heapify from top to bottom (parent to children)
//           Adjust  from bottom to top (children to parent)
class Solution {
	void adjust(vector<int> &A, int c){
		for(int p=(c-1)>>1; A[p]>A[c]; c=p, p=(c-1)>>1)
			swap(A[p],A[c]);
	}

public:
	/**
	 * @param A: Given an integer array
	 * @return: void
	 */
	void heapify(vector<int> &A) {
		// write your code here
		for(int i=0; i<A.size(); adjust(A,i++));
	}
};

// Method 2, Heapify from bottom to top (parent to top)
//           Adjust  from top to bottom (parent to children)
class Solution {
	void adjust(vector<int> &A, int p, int n){
		for(int id=p; p<n>>1; p=id){
			if ((p<<1)+1<n && A[(p<<1)+1]<A[id]) id=(p<<1)+1;
			if ((p<<1)+2<n && A[(p<<1)+2]<A[id]) id=(p<<1)+2;
			if (id==p) break;
			swap(A[id],A[p]);
		}
	}

public:
	/**
	 * @param A: Given an integer array
	 * @return: void
	 */
	void heapify(vector<int> &A) {
		// write your code here
		int n = A.size(), i;
		for(i=(n>>1); i--; adjust(A,i,n));
	}
};
